|
N皇后问题——Python解决（超详细注释）
N皇后问题1、问题2、思路1）棋盘表示2）不攻击检查3）dfs搜索实现
3、代码总体实现4、结果展示
N皇后问题
前一段时间老师让我们做一道N后的算法题，对于刚学算法的我来说确实有亿点点困难，于是就开始查看力扣和csdn上大佬们的代码，下面是我对这道题的理解，希望可以对在这道题上有疑问的同学们有所帮助。（代码我参考了其他大佬们的，便于理解进行了一些些改动，如有侵权，可联系解决）
1、问题
n 后问题研究的是如果将 n 个皇后放置在一个 n×n 的棋盘上，使皇后彼此之间不能相互攻击（已知在同一行、同一列或者同一条斜线上，皇后之间都会相互攻击）。
2、思路
1）棋盘表示
我们用一个一维列表来表示棋盘，列表长度表示总行数，对应的数值表示皇后所在的是第几列。 比如 li = [1, 3, 0, 2] 即表示：棋盘是4行 * 4列，在第 1 行的第 2 个位置上 (因为[0] = 1) 存在一个皇后，同理，在第 2 行的第 4 个位置上 (因为li[1] = 3) 存在一个皇后，在第 3 行的第 1 个位置上 (因为li[2] = 0) 存在一个皇后，在第 4 行的第 3 个位置上 (因为li[3] = 2) 存在一个皇后。 
2）不攻击检查
是否处于同一列中是否在左斜线上：（行 + 列）的值不可相等是否在右斜线上：（列 - 行）的值不可相等
# 参数：当前列 位置总结果 当前行
def check(col, res, row):
# 遍历已经放好皇后的所有行（不用判断是否在同一行，因为一行有值后，会进行到下一个 dfs）
for i in range(row):
# 1、是否在同一列中 2、左斜线：（行 + 列）的值相等 3、右斜线：（列 - 行）的值相等
if res[i] == col or res[i] + i == row + col or res[i] - i == col - row:
return False
return True
3）dfs搜索实现
结束条件：当前行数 = 皇后总数，即最后一行已经成功放入皇后循环一行中的每一个位置，若不发生攻击事件，可将皇后放入该位置，即将该位置的值赋成列数继续下一行的搜索，即传入的参数为当前行数 + 1
# 参数：皇后总数 位置总结果 当前放置第几行
def dfs(num, res, row):
# 如果当前行数 = 皇后总数，结束跳出
if row == num:
print(res)
return
# 遍历 row 行中的每一列，判断是否可行
for col in range(num):
# 若可行
if check(col, res, row):
# 将该 row 行的数值改成列数 col
res[row] = col
# 进行下一行的搜索
dfs(num, res, row + 1)
# 若进行到这一步说明，上一步走后，后续无法再放置皇后，需要回溯
# 也可以不回溯，因为进入下一个循环（将该 row 行的数值改成列数 col + 1）后，会重新对 res[row] 赋值
res[row] = 0
3、代码总体实现
def dfs(num, res, row):
if row == num:
print(res)
return
for col in range(num):
if check(col, res, row):
res[row] = col
dfs(num, res, row + 1)
res[row] = 0
def check(col, res, row):
for i in range(row):
if res[i] == col or res[i] + i == row + col or res[i] - i == col - row:
return False
return True
if __name__ == '__main__':
# num: 皇后的数量
num = int(input('请输入皇后的数量：'))
# 最终皇后的位置 （下标：第几行 数值：第几列）
res = [0 for _ in range(num)]
# 从第一行开始
row = 0
# 参数：皇后总数 位置结果 当前放置第几行
dfs(num, res, row)
4、结果展示
棋盘及皇后位置：   最后，相信大家也看出来了，这两种情况就是将棋盘翻转了以下，位置都是差不多的。
|